package com.chenyi.data.structure.linked;

/**
 * @author by chenyi
 * @className SingleLinkedList
 * @date 2021/12/21 14:40
 */
public class SingleLinkedList {

    /**
     * 头节点
     */
    private final Node first = new Node(null, null);

    /**
     * 尾节点
     */
    private Node last;

    /**
     * 长度
     */
    private int size;

    /**
     * 添加
     *
     * @param e
     * @return
     */
    public boolean add(int e) {
        // 判断是否为第一次添加
        if (first.next == null) {
            first.next = new Node(e, null);
            last = first.next;
        } else {
            last.next = new Node(e, null);
            last = last.next;
        }
        size++;
        return true;
    }

    /**
     * 根据index进行插入
     * @param e
     * @param index
     * @return
     */
    public boolean add(int e, int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        // 获取要插入index的上一个节点
        Node prevNode = prevNode(index);
        // 保存要插入index的下一个节点
        Node nextNode = prevNode.next;
        // 将上一个节点连接当前要插入的值，并且连接下一个节点
        prevNode.next = new Node(e, nextNode);
        size++;
        return true;
    }

    /**
     * 获取倒数第index位的值
     * @param index
     * @return
     */
    public Node getLastLinkedByIndex(int index) {
        Node node = first.next;
        for (int i = 0; i < size - index; i++) {
            node = node.next;
        }
        return node;
    }

    /**
     * 反转链表
     * @return
     */
    public boolean reversalLinked() {
        Node prevNode = first.next;
        Node lastNode = null;
        Node newHead = new Node(null, null);
        while (prevNode != null) {
            lastNode = prevNode.next;
            prevNode.next = newHead.next;
            newHead.next = prevNode;
            prevNode = lastNode;
        }
        first.next = newHead.next;
        return true;
    }

    /**
     * 删除
     * @param index
     * @return
     */
    public boolean remove(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        // 获取当前节点的上一个节点
        Node prevNode = prevNode(index);
        // 保存当前节点
        Node node = prevNode.next;
        // 让当前节点的上一个节点与当前节点的下一个节点连接
        prevNode.next = prevNode.next.next;
        size--;
        node = null;
        return true;
    }

    public boolean update(int e, int index) {
        // 获取当前节点的上一个节点
        Node prevNode = prevNode(index);
        prevNode.next.element = e;
        return true;
    }

    /**
     * 遍历获取当前节点上一个node
     * @param index
     * @return
     */
    private Node prevNode(int index) {
        Node node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }


    /**
     * 遍历
     */
    public void showLinked() {
        Node last = first;
        while (true) {
            if (last.next != null) {
                System.out.println(last.next);
                last = last.next;
            } else {
                break;
            }
        }
    }

    /**
     * 获取链表长度
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断index是否越界
     * @param index
     * @return
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    /**
     * 节点
     */
    private static class Node {
        private Integer element;
        private Node next;

        public Node(Integer element, Node next) {
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    '}';
        }
    }
}
